1. Field of the Invention
The present invention relates to an RSA cryptographic processing apparatus for an IC card, and more particularly, to an RSA cryptographic processing apparatus for an IC card capable of performing an RSA cryptographic algorithm among public key cryptographic algorithms used for providing the security to protect the private information of card's users and prevent the important information of the card from being appropriated. The present invention may be embodied, for example, in an IC card system, but it will be appreciated that it is also useful in other applications, such as miniature packages including a cryptographic processor, expensive electronic appliances and so forth, requiring a function of authenticating the identification of a user and restricting the access of an unrelated person, if necessary.
2. Background of the Related Art
Generally, IC cards or smart cards are commonly known as a card capable of storing, managing and processing the information therein by use of built-in processor and memory Since such cards have the excellent security characteristic which is not provided by general magnetic strip cards or memory cards, the cards are used in combination with various card readers, such as computer, passage controller, mobile phone and so forth, so as to control the access to the information resources. In particular, the cards are applied to various information communication services such as electronic commerce, traffic, broadcasting and so forth. The IC card provides a cryptographic function to provide the security suitable for the use condition in various application fields as described above. RSA cryptographic algorithm among public key cryptographic algorithms which are widely used in the IC cards is an asymmetric cryptographic algorithm for cryptographic operation or digital signature. In order to provide the transaction using the cards with the security, the RSA cryptographic algorithm is employed in Visa, Mastercard and EMV card system, for example, in the form of Secure Electronic Transaction protocol.
The operation of the RSA cryptographic algorithm is performed by the modular exponentiation operation of which the operation process called as modular multiplication represented by Equation 1 is iteratively executed.
Equation 1
RSA public key encrypting/decrypting algorithm
Encryption in case of sending a message m from “B” to “A”:                1. obtain a public key (n, e)        2. represent the message m by a constant between [0, n−1]        3. compute c=me mod n        4. send the generated ciphertext c to “A”        
Decryption of A receiving the message c:                1. compute m=cd mod n using a private key        
Specifically, the basic operation of the RSA algorithm is an iterative modular multiplication operation on a large number above 512 to 1024 bits, as will be known from step 3 in Equation 1. With respect to two numbers A and B, and a modular value M, assuming the residual which is left when a multiplied result of A and B is divided by M is C, the modular multiplication may be represented by the following Equation 2.
                    C        =                              AB            ⁢                                                  ⁢            mod            ⁢                                                  ⁢            M                    =                      AB            -                                          [                                  AB                  M                                ]                            ⁢              M                                                          Equation        ⁢                                  ⁢        2            
Among several algorithms performing the modular multiplication of Equation 2, a Montgomery algorithm is widely used because of performing the modular operation using only multiplication and addition, without using division operation needing a lot of time.
According to Montgomery algorithm, the arbitrary constant A is transformed into AR mod M which is a residual class number system of the constant M on the constant R generated by modulus M, and the modular operation is performed in the new transformed set. At that time, the constant R is selected by a prime constant larger than M. The Montgomery modular multiplication algorithm for performing the modular multiplication is represented by the following Equation 3.
Equation 3
Montgomery modular multiplication: ABR-1                1. S=0        2. iterate the following steps on i from zero to (n−1)        3. begin        4. Qi=((S0+AiB0)(r−M0)−1) mod r        5. S=(S+AiB+QiM) div r        6. end        7. if S≧M, compute S=S−M        
Since the Montgomery multiplication operation shown in Equation 3 transforms the original number system into a residual class number system, this may not be applied to the RSA cryptographic algorithm of Equation 1. The calculation of the RSA cryptographic algorithm using the Montgomery multiplication is performed by use of a Montgomery exponentiation algorithm such as Equation 4.
Equation 4
Input: m=(mn−1 . . . m1m0)r, xp=xR mod m, A=R mod m, e=(et . . . e1e0)2.
Output: xe mod m                1. iterate the following steps from t to zero        2. A=Mont(A, A)        3. if ei=1, A=Mont(A, xP)        4. A=Mont(A, t)        
As will be known from Equation 4, the RSA cryptographic operation using the Montgomery modular exponentiation operation performs iteratively the Montgomery modular exponentiation operation represented by Mont( ) according to a exponent value.
When calculating a value S, since the Montgomery modular multiplication operation shown in Equation 3 is performed by the estimation on the result value, the result value S of the operation may be an actual result value of the modular multiplication operation or be larger as much as modulus M than the actual result value. Accordingly, in order to obtain the actual result value of the Montgomery modular multiplication, the last compensating step such as step 7 has to be required.
As described above, according to an RSA cryptographic processing circuit using the Montgomery modular exponentiation operation, since an operating unit is large, i.e., the data to be processed at once is above 512 to 1024 bits, a register or memory region for storing an intermediate value generated at the operation process has to employ a large space above 512 to 1024 bits. In this case, the more the registers required for storing the data, modulus values and the exponent values (key values of user) to be inputted for the RSA cryptographic operation be increased, the more the size of the circuit is increased. Also, the more the number of memories is used, the more access times of the memory to store or read the data in the memory is increased. Therefore, since the speed of performing the cryptographic operation is reduced, there is a disadvantage that it is unsuitable for the IC card requiring the small size and fast cryptographic circuit.